import random

from utils.log import Log
from algo.tree.tree_serialize import TreeSerialize
from utils.qs import QS


# Tarjan算法解决lca的批量查询、树链剖分算法解决lca的在线查询，会在【扩展】课程讲述


class LCA(Log):
    def __init__(self):
        # ref: https://www.bilibili.com/video/BV1194y16727/?spm_id_from=333.999.0.0&vd_source=ad559e41b561d48861f70d0187e51e02
        # 00:00:00
        super(LCA, self).__init__()

    def lca(self, root, node1, node2):
        if (root is None) or (node1 is None) or (node2 is None) \
                or (root == node1) or (root == node2):
            return root

        left = self.lca(root.left, node1, node2)
        right = self.lca(root.right, node1, node2)
        if left and right:
            return root
        if not left and not right:
            return None
        return left if left else right


if __name__ == '__main__':
    q = QS()
    random_list = []
    t = TreeGenerator().do()
    q.push(t)
    while len(q):
        n = q.pop()
        random_list.append(n)
        if n.left:
            q.push(n.left)
        if n.right:
            q.push(n.right)
    node1 = random.choice(random_list)
    node2 = random.choice(random_list)
    print(f"select {node1} and {node2} to get lca")
    print(TreeSerialize.serialize(t))

    print('lca is', LCA().lca(t, node1, node2))
